/*!
 Temelia - binary tree common interface.

 This is an internal interface used by binary trees, binary search trees and self-balancing
 binary trees. Because C is not an OOP language this is how I simulate the inheritance,
 in order to share primitives to different binary trees.
 Methods from binary tree interface, binary search tree and self-balancing binary trees
 interfaces delegates methods in this interface to do the job.

 Copyright (C) 2008, 2009 Ceata (http://cod.ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#ifndef BINARY_TREE_COMMON_H_
#define BINARY_TREE_COMMON_H_

#include "common.h"

struct _bt_node_t;

// Internal definitions
typedef struct _bt_node_t *_binary_tree_t;
typedef struct _bt_node_t *_binary_tree_node_t;
typedef struct _bt_node_t *_binary_search_tree_t;
typedef struct _bt_node_t *_binary_search_tree_node_t;

// Binary tree
typedef _binary_tree_t binary_tree_node_t;
typedef _binary_tree_node_t binary_tree_t;

// Binary search tree
typedef _binary_tree_t binary_search_tree_t;
typedef _binary_tree_node_t binary_search_tree_node_t;

// AVL tree
typedef _binary_tree_t avl_tree_t;

// Red-black tree
typedef _binary_tree_t red_black_tree_t;

// Treap
typedef _binary_tree_t treap_tree_t;

// Scapegoat
typedef _binary_tree_node_t scapegoat_node_t;

// Splay
typedef _binary_tree_t splay_tree_t;

/*!
 * @see binary_tree_new
 */
_binary_tree_t _binary_tree_new(void *key);

/*!
 * @see binary_tree_delete_node.
 */
void _binary_tree_delete_node(_binary_tree_node_t node);

/*!
 * @see binary_tree_delete
 */
void _binary_tree_delete(_binary_tree_t tree);

/*!
 * @see binary_tree_compare_trees
 */
int _binary_tree_compare_trees(_binary_tree_t bt1, _binary_tree_t bt2, int compare(
		void *x, void *y, void *context), void *context);

/*!
 * @see binary_tree_is_empty
 */
int _binary_tree_is_empty(_binary_tree_t tree);

/*!
 * @see binary_tree_is_leaf
 */
int _binary_tree_leaf(_binary_tree_t node);

/*!
 * @see binary_tree_get_size
 */
int _binary_tree_get_size(_binary_tree_t tree);

/*!
 * @see binary_tree_get_root
 */
_binary_tree_t _binary_tree_get_root(_binary_tree_t node);

/*!
 * @see binary_tree_get_key
 */
void *_binary_tree_get_key(_binary_tree_t node);

/*!
 * @see binary_tree_set_key
 */
void _binary_tree_set_key(_binary_tree_t node, void *key);

/*!
 * @see binary_tree_get_parent
 */
_binary_tree_t _binary_tree_get_parent(_binary_tree_t node);

/*!
 * @see binary_tree_set_parent
 */
void _binary_tree_set_parent(_binary_tree_t node, _binary_tree_t parent, int dir);

/*!
 * @see binary_tree_get_left_child
 */
_binary_tree_t _binary_tree_get_left_child(_binary_tree_t node);

/*!
 * @see binary_tree_set_left_child
 */
void _binary_tree_set_left_child(_binary_tree_t node, _binary_tree_t child);

/*!
 * @see binary_tree_get_right_child
 */
_binary_tree_t _binary_tree_get_right_child(_binary_tree_t node);

/*!
 * @see binary_tree_set_right_child
 */
void _binary_tree_set_right_child(_binary_tree_t node, _binary_tree_t child);

/*!
 * @see binary_tree_join
 */
void _binary_tree_join(_binary_tree_t parent, _binary_tree_t left,
		_binary_tree_t right);

/*!
 * @see binary_tree_split
 */
void _binary_tree_split(_binary_tree_t parent, _binary_tree_t *left,
		_binary_tree_t *right);

/*!
 * @see binary_tree_create_node
 */
_binary_tree_t _binary_tree_create_node(_binary_tree_t parent, _binary_tree_t left,
		_binary_tree_t right, void *key, int dir);

/*!
 * @see binary_tree_get_height
 */
int _binary_tree_get_height(_binary_tree_t tree);

/*!
 * @see binary_tree_get_depth
 */
int _binary_tree_get_depth(_binary_tree_t node);

/*!
 * @see binary_tree_preorder
 */
void _binary_tree_preorder(_binary_tree_t tree, void key_handler(void *key,
		void *context), void *context);

/*!
 * @see binary_tree_inorder
 */
void _binary_tree_inorder(_binary_tree_t tree, void key_handler(void *key,
		void *context), void *context);

/*!
 * @see binary_tree_reverse_inorder
 */
void _binary_tree_reverse_inorder(_binary_tree_t tree, void key_handler(
		void *key, void *context), void *context);

/*!
 * @see binary_tree_postorder
 */
void _binary_tree_postorder(_binary_tree_t tree, void key_handler(void *key,
		void *context), void *context);

/*!
 * @see binary_tree_level_order
 */
void _binary_tree_level_order(_binary_tree_t tree, void key_handler(void *key,
		void *context), void *context);

/*!
 * @see binary_tree_show_indented
 */
void _binary_tree_show_indented(_binary_tree_t tree, void key_handler(void *key,
		int level, void *context), void *context, int level);

/*!
 * @see binary_search_tree_search
 */
_binary_search_tree_node_t _binary_search_tree_search(binary_search_tree_t bst,
		void *key, int compare(void *x, void *y, void *context), void *context);

/*!
 * @see binary_search_tree_insert
 */
_binary_search_tree_node_t _binary_search_tree_insert(binary_search_tree_t bst,
		void *key, int compare(void *x, void *y, void *context), void *context);

/*!
 * @see binary_search_tree_remove
 */
_binary_search_tree_node_t _binary_search_tree_remove(binary_search_tree_t *bst,
		void *key, int compare(void *x, void *y, void *context), void *context,
		binary_search_tree_t *my_deleted);

/*!
 * @brief binary_search_tree_get_min
 */
_binary_search_tree_node_t _binary_search_tree_get_min(binary_search_tree_t bst);

/*!
 * @see binary_search_tree_get_max
 */
_binary_search_tree_node_t _binary_search_tree_get_max(binary_search_tree_t bst);

/*!
 * @see binary_search_tree_next
 */
_binary_search_tree_node_t _binary_search_tree_next(binary_search_tree_t bst,
		_binary_search_tree_node_t node);

/*!
 * @see binary_search_tree_prev
 */
_binary_search_tree_node_t _binary_search_tree_prev(binary_search_tree_t bst,
		_binary_search_tree_node_t node);

/*!
 * @brief Rotates left the given tree and returns reference to new sub-tree's root
 * Complexity O(1)
 *
 * @param Binary search tree
 */
_binary_search_tree_node_t _self_balanced_binary_search_tree_rotate_left(
		_binary_search_tree_node_t tree);

/*!
 * @brief Rotates right the given tree and returns reference to new sub-tree's root.
 * Complexity O(1)
 *
 * @param Binary search tree
 */
_binary_search_tree_node_t _self_balanced_binary_search_tree_rotate_right(
		_binary_search_tree_node_t tree);

/*!
 * @brief Double left rotation.
 * Complexity O(1)
 *
 * @param Binary search tree
 */
_binary_search_tree_node_t _self_balanced_binary_search_tree_rotate_left_double(
		_binary_search_tree_node_t x);

/*!
 * @brief Double right rotation.
 * Complexity O(1)
 *
 * @param Binary search tree
 */
_binary_search_tree_node_t _self_balanced_binary_search_tree_rotate_left_double(
		_binary_search_tree_node_t x);

struct _bt_node_t
{
	/*! key in node */
	void *key;

	/*! pointer to parent */
	struct _bt_node_t *parent;

	/*! pointer to left child */
	struct _bt_node_t *left;

	/*! pointer to right child */
	struct _bt_node_t *right;
};

#endif /* BINARY_TREE_COMMON_H_ */
